#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define MAX(a, b) (a) > (b) ? (a) : (b)
#define MIN(a, b) (a) < (b) ? (a) : (b)

typedef struct MyStruct
{
    int value;
    int index;
} mystruct;

int binary_search(mystruct *nums, int pos, int numsSize, int target)
{

    int l = pos, r = numsSize - 1, mid = 0;

    while (l <= r)
    {
        mid = l + (r - l) / 2;
        if (nums[mid].value == target)
            return mid; //nums[mid].index;
        else if (nums[mid].value > target)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return -1;
}

int cmp(const void *a, const void *b)
{
    return (*(mystruct *)a).value - (*(mystruct *)b).value;
}

// 暴力法 + qsort + 二分查找
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{

    if (nums == NULL)
        return NULL;

    int *res = (int *)malloc(sizeof(int) * 2);
    mystruct *myst = (mystruct *)malloc(sizeof(mystruct) * numsSize);
    for (int i = 0; i < numsSize; i++)
    {
        myst[i].value = nums[i];
        myst[i].index = i;
    }

    *returnSize = 2;
    qsort(myst, numsSize, sizeof(mystruct), cmp);
    // for(int i=0;i<numsSize;i++) {
    //     printf("myst[%d] = %d, %d\n",i, myst[i].value, myst[i].index);
    // }

    for (int i = 0; i < numsSize; i++)
    {

        int mid = binary_search(myst, i + 1, numsSize, target - myst[i].value);
        if (mid != -1)
        {
            res[0] = MIN(myst[i].index, myst[mid].index);
            res[1] = MAX(myst[i].index, myst[mid].index);
            break;
        }
    }

    free(myst);
    return res;
}

int main()
{
    int test[8] = {2, 7, 11, 15, 3, 5, 6, 13};
    int *list;
    int returnVal;
    list = twoSum(test, 8, 28, &returnVal);
    for (int i = 0; i < returnVal; i++)
    {
        printf("%d,", test[i]);
    }
    printf("\n");
    free(list);
}